//: [Previous](@previous)
/**
 
 #3 [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
 
 Given a string, find the length of the **longest substring** without repeating characters.
 
 给定一个字符串，找出不含有重复字符的最长子串的长度。
 
 Example 1:
 ```
 Input: "abcabcbb"
 Output: 3
 Explanation: The answer is "abc", with the length of 3.
 ```
 
 Example 2:
 ```
 Input: "bbbbb"
 Output: 1
 Explanation: The answer is "b", with the length of 1.
 ```
 
 Example 3:
 ```
 Input: "pwwkew"
 Output: 3
 Explanation: The answer is "wke", with the length of 3.
 Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
 ```
 
 T: O(n)
 S: O(1)
 
 */
import Foundation

class Solution {
    // 1. 定义一个 256 长度 的数组
    // 2. 将字符串转换为 ASCII码 数组
    // 3. 遍历存储当前字符所处的坐标，计算长度
    // 4. 遍历更新查找最大长度
    func lengthOfLongestSubstring(_ s: String) -> Int {
        // 存储 256 个字符
        var hash = Array(repeating: -1, count: 256)
        // 将字符串转换为 ASCII码 数组
        let strings = Array(s.utf16).map { Int($0) }
        var length = 0, left = -1
        
        for (i, num) in strings.enumerated() {
            left = max(left, hash[num])
            hash[num] = i
            length = max(length, i - left)
        }
        return length
    }
    
    // 就是使用字典来存储
    func lengthOfLongestSubstring2(_ s: String) -> Int {
        var hashMap = [Int: Int]()
        var strings = Array(s.utf16).map { Int($0) }
        var length = 0, left = -1
        for (i, num) in strings.enumerated() {
            if let lastPosition = hashMap[strings[i]] {
               left = max(left, lastPosition)
            }
            
            hashMap[num] = i
            length = max(length, i - left)
        }
        return length
    }
}

print(Solution().lengthOfLongestSubstring("abcabcbb"))
print(Solution().lengthOfLongestSubstring("bbbb"))
print(Solution().lengthOfLongestSubstring("pwwkew"))

print(Solution().lengthOfLongestSubstring2("abcabcbb"))
print(Solution().lengthOfLongestSubstring2("bbbb"))
print(Solution().lengthOfLongestSubstring2("pwwkew"))

//: [Next](@next)
